#include <iostream>

using namespace std;

long long powModel(int a, int d, int n)
{
	long long tempA = a;
	long long single = 1;
	while (d > 1) {
		if (d % 2 == 1) {
			single = (single * tempA) % n;
		}
		tempA = (tempA * tempA) % n;
		d /= 2;
	}

	tempA = (single * tempA) % n;
	
	return tempA;
}

bool isPrimable(int base, int d, int r, int n) 
{
	long long model = powModel(base, d, n);
	if (model == 1 || model == n - 1)
		return true;

	for (int i = 0; i < r; i++) {
		model = ((model % n) * (model % n)) % n;
		if (model == n - 1)
		{
			return true;
		}
	}

	return false;
}

bool isPrimable(int n) 
{
	if (n < 10) {
		for (int i = 2; i <= n / 2; i++) {
			if (n % i == 0) {
				return false;
			}
		}

		return true;
	}
	int d = -1, r = 0;
	int origin = n;	
	--n;
	while (n > 0) {
		if (n % 2 == 0) {
			n /= 2;
			++r;
		} else {
			d = n;
			break;
		}
	}

	n = origin;
	int base = 2;
	if (isPrimable(base, d, r, n)) {
		if (n <= 3)
			base = 2;
		else
			base = 3;
		if (isPrimable(base, d, r, n)) {
			return true;
		}
	}
	return false;
}

int nextPrime(int n)
{
	while (true) {
		if (n == 2) {
			++n;
		} else  {
			n += 2;
		}
		if (isPrimable(n))
			return n;
	}
}

int main(int argc, char* args[])
{
	int n;
	int next = 2, pre = -1, aft = -1;
	while (cin>>n && n != 0) {
		/*next = 2;
		pre = next;
		while (true) {
			if (n == next) {
				cout<<0<<endl;
				break;
			} else if (n > next) {
				pre = next;
				next = nextPrime(next);
			} else {
				cout<< next - pre<<endl;
				break;
			}
		}*/
		int origin = n;
		while (n >= 2) {
			if (isPrimable(n)) {
				pre = n;
				break;
			}
			if (n % 2 == 0)
				--n;
			else
				n -= 2;
		}

		n = origin;
		while (true) {
			if (isPrimable(n)) {
				aft = n;
				break;
			}
			if (n % 2 == 0)
				++n;
			else 
				n += 2;
		}
		cout<<aft - pre<<endl;

	}
	return 0;
}